package com.jia.leetCode;

public class Pro0718 {
    public int findLength(int[] A, int[] B) {
        if(A.length == 0 || B.length == 0) return 0;
        //dp[i][j]
        //dp[i][j] = dp[i-1][j-1] + 1 ,A[i] == B[j]
        //dp[i][j] = max{dp[i][j], dp[i-1][j], dp[i][j-1]}
        int[][] dp = new int[A.length][B.length];
        int max = 0;
        for(int i = 0; i < A.length; i++) {
            for(int j = 0; j < B.length; j++) {
                if(A[i] == B[j]) {
                    if(i - 1 < 0 || j - 1 < 0) {
                        dp[i][j] = 1;
                    }else {
                        dp[i][j] = dp[i - 1][j - 1] + 1;
                    }
                }
                max = Math.max(dp[i][j], max);
            }
        }
        return max;

    }

    public static void main(String[] args) {
        Pro0718 pro0718 = new Pro0718();
        int[] A = {1,2,3,2,1};
        int[] B = {3,2,1,4,7};
        pro0718.findLength(A, B);
    }
}
